package com.sicheng.lc.周赛.分类.dp.数位;

import java.util.ArrayList;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/18 21:04
 */
public class 不含连续1的非负整数 {
    //https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/

    static int N = 32;
    // dp[i,j] 一共i位最高位为j 不含连续1的个数
    // j 只能是 [0,1]
    static int[][] dp = new int[N + 1][2];

    static {
        for (int i = 0; i <= 1; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= N; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
            dp[i][1] = dp[i - 1][0];
        }
    }

    public int findIntegers(int n) {

        ArrayList<Integer> nums = new ArrayList<>();
        while (n != 0) {
            nums.add(n & 1);
            n >>= 1;
        }
        int res = 0;
        int last = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            for (int j = 0; j < x; j++) {
                res += dp[i + 1][j];
            }

            if ((last & x) == 1)
                break;

            last = x;

            if (i == 0)
                res++;

        }

        return res;
    }
}
